#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<math.h>

//4.1 地图节点结构体实现
#define NAMESIZE 20                         //名称允许长度
#define TRUE 1                              //定义符号常量“真”
#define FALSE 0                             //定义符号常量“假”
typedef int STATUS;
typedef char NODETYPE[NAMESIZE];            //节点名称类型
typedef struct NODE
{
    NODETYPE name;
    int x,y;
    float evaluate;
    double step;
}NODE;
typedef struct NEIGHBORNODE          //节点类型
{
    NODE node;                       //节点
    struct NEIGHBORNODE *next;       //邻近节点
}NEIGHBORNODE,*NEIGHBOR;             //相邻节点类型【*NEIGHBOR和下文中*PATH均为指向NEIGHBORNODE的指针】
typedef struct ANODE                 //节点类型
{
    NODE node;                       //节点
    NEIGHBOR adjacents;              //邻近节点
}ANYNODE;                            //节点类型【将ANODE重命名为ANYNODE】
typedef struct GRAPHNODE             //图的节点的存储类型
{
    ANYNODE node;                    //节点
    struct GRAPHNODE *next;          //其他节点
}GRAPHNODE,*GRAPH;                   //图类型【*GRAPH为指向GRAPHNODE的指针】

typedef struct NEIGHBORNODE *PATH;   //路径类型

typedef struct Paths                 //路径集合类型
{
    PATH path;                       //一条路径
    struct Paths *next;              //下一条路径
}Paths,*PATHS;                       //路径集合类型【*PATHS为指向PATH的指针】

typedef struct Paths *STACK;         //定义堆栈类型，实际上也是节点链表【相邻节点链表】

//3.2 图存储实现

/*
//3.2.1 通用比较函数
int Equal(NODE n1,NODE n2, int *fun())
{
    return (int)fun(n1,n2);
}//判断图的两个节点是否相同，若相同则为1，否则则为0

//3.2.2 通用赋值函数
void Set (NODE n1,NODE n2,void *fun())
{
    fun(n1,n2);
}
*/

//4.2.1 对地图节点的赋值
void Set(NODE *node1,NODE *node2)
{
    strcpy(node1->name,node2->name);
    node1->x=node2->x;
    node1->y=node2->y;
    node1->evaluate=node2->evaluate;
    node1->step=node2->step;
}

//4.2.2 九宫位置查找
void GetPos(GRAPH graph,NODE* current)
{
    GRAPH t=graph;
    while(t->next!=NULL)
    {
        if(strcmp(t->node.node.name,current->name)==0)
        {
            break;
        }
        t=t->next;
    }
    current->x=t->node.node.x;
    current->y=t->node.node.y;
}

//3.2.3 相邻节点关系的构建
NEIGHBOR Add_A_Adjacents(NEIGHBOR br,NODE node)        //Add_A_Adjacents把一个节点加入到相邻节点群中
{
    NEIGHBOR b,pb;                                  //相邻节点
    b=(NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE)); //动态开辟一个相邻节点
    Set(&(b->node),&node);                           
    b->next=NULL;
    if(br==NULL)                                    //没有相邻节点的情况
    {
        br=b;                                       //node就是第一个邻居
    }
    else                                            //有相邻节点的情况
    {
        pb=br;                                      //node就是最后一个相邻节点【值在b中，头插入】
        while(pb->next)   pb=pb->next;
        pb->next=b;
    }
    return br;                                      //返回相邻节点【指针】
}

//3.2.8 字符数值转换
//把字符串的字符'/'转换为转义字符'\0'(字符串结束标志)，故需要在字符串数组中存放多个节点名称(相邻节点)的字符串
void CreateStr(char *neighborset)  //字符数组转换为多个字符串
{
    char *c=neighborset;           //临时字符串
    while(*c)
    {
        if(*c=='/')  *c='\0';     //插入字符串结束标志
        if(*c==',')  *c='\0';
        c++;
    }
    c++;
    *c='\0';                      //多一个结束标记
}

//3.2.9 字符数组建立相邻关系
//把字符串数组中的多个相邻节点节点名称建立成图的相邻节点群(链表)
NEIGHBOR CreateNeighbors(NEIGHBOR neighbors,char *neighborset)   //若干个节点构成相邻节点
{
    char *p=neighborset;                                         //多个节点，分隔符'/'
    char temp[20];
    NODE node;
    CreateStr(neighborset);                                      //变成多个字符串
    while(*p)
    {
        strcpy(node.name,p);
        p+=strlen(node.name)+1;                                  //下一个节点
        strcpy(temp,p);
        sscanf(temp, "%d", &node.x);
        p+=strlen(temp)+1;
        strcpy(temp,p);
        sscanf(temp, "%d", &node.y);
        p+=strlen(temp)+1;
        node.evaluate=0;
        node.step=0;
        neighbors=Add_A_Adjacents(neighbors,node);          //加入相邻关系中
    }
    return neighbors;                                       //返回相邻节点链表
}

//3.2.4 双亲与子节点关系的构建
//subgraph=Form_Pa_Ch(neighbors,adjacents);             //构建子图
GRAPH Form_Pa_Ch(char *neighbors,NEIGHBOR br)                   //将相邻节点(所有子节点)链接到双亲节点中，构成一个子树
{
    GRAPH graph;
    graph=(GRAPH)malloc(sizeof(struct GRAPHNODE));   //创建双亲节点
    NEIGHBOR temp=NULL;
    temp=CreateNeighbors(temp,neighbors);                             //TODO:对目标节点进行相同处理
    Set(&(graph->node.node),&(temp->node));
    graph->next=NULL;
    graph->node.adjacents=br;                        //相邻节点与双亲节点构成子图
    return graph;                                    //返回带相邻节点的双亲结点，即子图
}

//3.2.5 将带子节点的双亲节点加入到图中
GRAPH Add_A_Sub_Graph(GRAPH graph,GRAPH subgraph) //将双亲结点加入到图中
{
    GRAPH t=graph;                        //临时图
    if(graph==NULL)                       //图不存在
    {
        graph=subgraph;                   //带子节点的双亲节点即为图
    }
    else                                  //图存在
    {
        while(t->next)  t=t->next;
        t->next=subgraph;                 //带子节点的双亲节点加入到图的最后
    }
    return graph;                         //返回图指针
}//graph是链式队列，通过上述程序实现子图subgraph(相邻结点)进队列过程

//3.2.6 清除相邻节点和图
NEIGHBOR ClearNeighbors(NEIGHBOR br)  //回收相邻节点空间
{
    NEIGHBOR br1=br;                 //临时相邻变量
    while(br)                        //【遍历相邻节点】
    {
        br1=br;
        br=br->next;                //【挨个变量赋给临时指针】
        free(br1);                  //回收单元
        return br;
    }
    return br;                      //返回NULL
}

//3.2.7 清空图并回收数据单元
GRAPH ClearGraph(GRAPH graph)
{
    GRAPH graph1=graph;              //临时图
    while(graph)                     //【遍历双亲节点】
    {
        graph1=graph;
        graph=graph->next;          //【挨个变量赋给临时指针】
        free(graph1);               //回收单元
    }
    return graph;
}//在程序运行结束前需要动态回收动态开辟的数据单元
//以上两个程序实际上是出队列过程，只是没有返回值

//3.2.10 根据图文件建立图
//图文件为txt文件，其记录格式为单数行为双亲节点，偶数行为子节点，用字符'/'分隔符分开
GRAPH CreateGraph(GRAPH graph,char *filename)               //从文件创建图
{
    GRAPH subgraph;
    NEIGHBOR adjacents;
    FILE *fp;
    char neighbors[200],neighborset[5000];
    fp=fopen(filename,"r");
    while(!feof(fp))                                        //文件中是否还存在图的节点名称
    {
        fscanf(fp,"%s",neighbors);                          //读入选中节点
        fscanf(fp,"%s",neighborset);                        //读入若干相邻节点(子节点)，分隔符'/'
        adjacents=NULL;
        adjacents=CreateNeighbors(adjacents,neighborset);    //构建相邻节点
        subgraph=Form_Pa_Ch(neighbors,adjacents);             //构建子图
        graph=Add_A_Sub_Graph(graph,subgraph);             //图中加入子图
    }
    fclose(fp);                                              //关闭文件
    return graph;                                            //返回所建的图
}

//3.3.1 复制子节点集
//复制所有节点（链表），返回复制结果的头指针，建立链式队列
NEIGHBOR CopyNeighbors(NEIGHBOR adjacents)                       //节点集复制
{
    NEIGHBOR copynode=NULL, lastnode=NULL, head = NULL;                        //没有子节点
    while (adjacents)
    {
        copynode = (NEIGHBOR)malloc(sizeof(struct NEIGHBORNODE));
        Set(&copynode->node, &adjacents->node);
        copynode->next = NULL;
        if (head == NULL)
        {
            head = copynode;                                       //第1个节点
        }
        else
        {
            lastnode->next = copynode;                             //非第1个节点：建立链接，复制子节点集
        }
        lastnode = copynode;
        adjacents = adjacents->next;                               //下一个子节点
    }
    return head;                                                 //返回头节点指针
}

//3.3.2 复制路径和路径集合
PATH CopyPath(PATH path)                               //复制一条路径，返回新路径
{
    PATH tempath;
    tempath=(PATH)CopyNeighbors((NEIGHBOR)path);       //路径与邻居节点集合相同
    return tempath;
}

PATHS CopyPaths(PATHS paths)                     //复制路径集合
{
    PATHS copynode=NULL, lastnode=NULL, head = NULL;
    while (paths)                                 //路径集合不为空
    {
        copynode = (PATHS)malloc(sizeof(Paths));   //路径节点
        copynode->path = CopyPath(paths->path);    //复制一条路径
        copynode->next = NULL;                     //复制路径初始化
        if (head == NULL)                           //第1条路径
        {
            head = copynode;
        }
        else                                     //非第1条路径
        {
            lastnode->next = copynode;
        }
        lastnode = copynode;                       //加入路径集合
        paths = paths->next;
    }
    return head;
}

//3.3.3 节点加入路径
PATH Add_A_Node_To_Path(NODE *node,PATH path)   //在路径中加入一个节点形成新的路径
{
    PATH p;
    p=(NEIGHBOR)malloc(sizeof(NEIGHBORNODE));
    Set(&p->node,node);                        //等价，赋值
    if(path==NULL)                            //第1个节点
    {
        p->next=NULL;
    }
    else                                      //非第1个节点
    {
        p->next=path;                         //加入到路径头部
    }
    path=p;                                   //路径倒序加入
    return path;                              //返回路径头部
}

//3.3.4 路径加入路径集合
PATHS Add_A_Path_To_Paths(PATH path, PATHS paths) //路径加入到路径集合中
{
    PATH copypath;
    PATHS ps = NULL, p;
    if (path == NULL)   return paths;                //没有路径
    copypath = CopyPath(path);                      //复制路径
    ps = (PATHS)malloc(sizeof(Paths));              //开辟路径集合节点
    ps->path = copypath;                            //复制的路径置入
    ps->next = NULL;
    if (paths == NULL)                               //路径集合为空
    {
        paths = ps;
    }
    else                                          //路径集合为非空，新路径节点放置最后
    {
        p = paths;
        while (p->next) p = p->next;
        p->next = ps;
    }
    return paths;
}

//3.3.5 路径进栈和所有节点进栈
PATHS Push_A_Path(PATHS stack,PATH path)     //一条路径进栈，把1条路径压入堆栈，返回堆栈头指针
{
    PATH tempath;
    PATHS st;
    tempath=CopyPath(path);                            //复制节点
    st=(PATHS)malloc(sizeof(Paths));                   //路径节点
    st->path=tempath;                                  //置路径于栈中
    if(stack==NULL)                                    //第1条路径
    {
        st->next=stack;
    }
    else                                               //非第1条路径，已有路径
    {
        st->next=stack;
    }
    stack=st;
    return stack;
}

PATHS PushPaths(PATHS stack,PATHS paths)  //所有路径进栈，把路径集合压入堆栈中，返回路径集合的头指针
{
    PATHS p,head;
    head=CopyPaths(paths);                           //复制路径集合
    p=head;
    if(p!=NULL)                                      //逐一加入栈中
    {
        while(p->next) p=p->next;
        p->next=stack;
        stack=head;
    }
    return stack;
}

//3.3.6 回收栈、回收路径和回收路径集合
STACK ClearStack(STACK stack)              //回收栈空间
{
    stack=(STACK)ClearNeighbors((NEIGHBOR)stack);   //清除所有节点，得到空指针
    return stack;                          //返回空指针
}
PATH ClearPath(PATH path)                     //回收路径空间，复用了回收兄弟节点的数据空间函数
{
    path=(PATH)ClearNeighbors((NEIGHBOR)path);  //路径与兄弟节点集合形式相同
    return path;
}
PATHS ClearPaths(PATHS paths)               //回收路径集合空间
{
    PATHS paths1=paths;
    while(paths)                              //所有路径
    {
        paths1=paths;
        ClearPath(paths1->path);              //回收一条路径空间
        paths=paths->next;                    //下一条路径
        free(paths1);
    }
    return paths;
}

//3.3.7 出栈与节点
PATHS Pop_A_Node(STACK stack,NODE node,PATH *path)  //出栈，从堆栈中弹出获取路径和路径的节点名称，并返回堆栈头指针
{
    PATHS p=stack;
    PATH tempath;
    if(p!=NULL)
    {
        tempath=p->path;                                //一条路径
        Set(&node,&(tempath->node));
        *path=CopyPath(tempath);                         //获取路径
        stack=p->next;                                  //栈顶变化
        free(p);                                        //删除路径 
    }
    return stack;                                       //返回栈顶
}

//3.3.8 扩展节点集
NEIGHBOR ExpandNodes(GRAPH tree,NODE pa)              //由节点获取所有子节点
{
    NEIGHBOR children=NULL;                           //孩子节点
    GRAPH t=tree;                                     //树
    while(t)                                          //节点不为空
    {
        if(strcmp(t->node.node.name,pa.name)==0)              //找到分支节点
        {
            children=CopyNeighbors(t->node.adjacents);
            break;
        }
        t=t->next;                                  //下一个双亲结点
    }
    return children;
}

//3.3.9 路径倒叙与显示
void RevPath(PATH path)                     //路径倒序，按树根倒目标节点的顺序
{
    int num = 0, i;
    NODE* nodes;
    PATH p = path;
    while (p)                                //统计路径节点的个数
    {
        p = p->next;
        num++;
    }
    nodes = (NODE*)malloc(num * sizeof(NODE)); //开辟一维数组
    for (i = 0, p = path; p; p = p->next, i++)         //读取路径节点置于数组中
    {
        Set(&nodes[i], &(p->node));
    }
    for (i = num - 1, p = path; p; p = p->next, i--)     //数组数据倒序置于路径中
    {
        Set(&(p->node), &nodes[i]);
    }
    free(nodes);                            //回收数组空间
}

void PriPath(PATH path)                     //显示路径
{
    int count=1;
    while(path!=NULL)
    {
        printf("Step=%.0f:%s,pos=(%d,%d),evaluate=%.2f\n",path->node.step,path->node.name,path->node.x,path->node.y,path->node.evaluate);
        path=path->next;
    }
    printf("\n");
    //priNeighbors((NEIGHBOR)path);             //路径与兄弟节点集合形式相同
}

//3.4.1 判断节点是否在路径中
STATUS IsInPath(NODE node, PATH path)                      //判断节点是否在路径中并返回真或假
{
    PATH p = path;
    STATUS flag = FALSE;                                    //节点是否在路径中的标识
    while (p)
    {
        if (strcmp(node.name, p->node.name) == 0)                       //node在路径中
        {
            flag = TRUE;
            break;
        }
        else                                              //node不在路径中
        {
            p = p->next;
        }
    }
    return flag;                                          //返回真/假
}

//3.4.2 删除在路径中的节点
NEIGHBOR DeleteNodeInPath(NEIGHBOR adjacents, PATH path)    //从节点集合adjacents中删除节点在路径path中的节点
{
    NEIGHBOR n1 = adjacents, n2=NULL;
    STATUS flag = FALSE;
    while (n1)                                              //遍历节点集合中的每个节点
    {
        flag = IsInPath(n1->node, path);                      //节点是否在路径中
        if (flag == TRUE)
        {
            if (n1 == adjacents)                              //待删除节点位于第一个
            {
                adjacents = n1->next;                        //下一个节点
                free(n1);                                  //删除当前节点
                n1 = adjacents;                              //其他节点
            }
            else                                           //待删除节点不在第一个
            {
                n2->next = n1->next;                         //NULL
                free(n1);                                  //删除当前节点
                n1 = n2->next;                               //NULL
            }
        }
        else
        {
            n2 = n1;                                          //下一个节点
            n1 = n1->next;
        }
    }
    return adjacents;
}

//3.4.3  相邻节点形成路径合集
PATHS FromPathsFromNodes(NEIGHBOR adjacents,PATH path,PATHS paths)   //节点集合中的每个节点（不在路径中）挨个加入路径，依次形成路径集合
{
    PATH tempath;
    adjacents=DeleteNodeInPath(adjacents,path);           //删除构成回路的节点
    while(adjacents)                                      //所有不构成回路的节点
    {
        tempath=CopyPath(path);                              //复制路径
        tempath=Add_A_Node_To_Path(&(adjacents->node),tempath); //在路径中加入一个节点
        paths=Add_A_Path_To_Paths(tempath,paths);            //新路径加入路径集合
        adjacents=adjacents->next;                           //下一个节点
    }
    return(paths);                                        //返回路径集合
}

//3.7.5 长度计算
long int LengthOfPath(PATH path)
{
    long int count=1;
    while(path!=NULL)
    {
        path = path->next;
        count++;
    }
    return count;
}

//4.2.2 节点启发信息评估
float Evaluate(NODE *node1,NODE *node2)
{
    int i,j;
    double res=0;
    res=sqrt((node1->x-node2->x)*(node1->x-node2->x)+(node1->y-node2->y)*(node1->y-node2->y));
    //TODO:更新了评估规则
    return res;
}

void EvaluateAdjacents(NEIGHBOR adjacents,NODE *node,NODE *end)
{
    NEIGHBOR br=adjacents;
    while(br)
    {
        br->node.evaluate=Evaluate(&(br->node),end);
        br->node.step=node->step+1;
        br=br->next;
    }
}

//4.2.3 对九宫格最优节点的获取   Heuristic:启发式的
STACK PopANode_Heuristic_by_Mini(STACK stack,NODE *node,PATH *path)
{
    STACK p=stack,p1=NULL,p2,p3;
    PATH tempath;
    double ev=1e100;
    if(p==NULL)   return stack;
    *path=NULL;
    while(p!=NULL)
    {
        tempath=p->path;
        if(tempath->node.evaluate+tempath->node.step<ev)
        {
            ev=tempath->node.evaluate+tempath->node.step;
            p2=p1;
            p3=p;
        }
        p1=p;
        p=p->next;
    }
    tempath=p3->path;
    Set(node,&(tempath->node));
    *path=CopyPath(tempath);
    if(p3==stack)
    {
        stack=p3->next;
    }
    else
    {
        p2->next=p3->next;
    }
    free(p3);
    return stack;
}

//4.2.4 启发式搜索算法
STATUS SearchPath_A(GRAPH graph,NODE *start,NODE *end,PATH *path)
{
    NODE node;
    NEIGHBOR adjacents;
    STACK stack=NULL; 
    STATUS flag=FALSE;
    PATH tempath=NULL;
    PATHS paths=NULL;
    if(graph==NULL) return flag;
    start->step=0;
    start->evaluate=Evaluate(start,end);
    tempath=Add_A_Node_To_Path(start,tempath);
    stack=Push_A_Path(stack,tempath);
    while(stack)
    {
        tempath=ClearPath(tempath);
        stack=PopANode_Heuristic_by_Mini(stack,&node,&tempath);
        if(strcmp(end->name,node.name)==0)
        {
            flag=TRUE;
            *path=CopyPath(tempath);
            break;
        }
        adjacents=ExpandNodes(graph,node);
        EvaluateAdjacents(adjacents,&node,end);
        paths=FromPathsFromNodes(adjacents,tempath,paths);
        stack=PushPaths(stack,paths);
        paths=ClearPaths(paths);
    }
    ClearStack(stack);
    return flag;
}

int main()
{
    NODE start,end;                                                //起始节点、目标节点
    PATH path=NULL;                                                //路径
    STATUS flag;                                                   //节点是否在图中
    GRAPH graph=NULL;                                              //图
    char *filename="D:\\Develop\\C-Main\\DS_LiGuohe\\Chapter4\\Chapter4-Exercise2.txt";//图文件
    graph=CreateGraph(graph,filename);                             //建立图存储结构
    printf("The Start Node:");
    scanf("%s",start.name);                                             //输入任一起点节点名
    GetPos(graph,&start);
    printf("The End Node:");
    scanf("%s",end.name);
    GetPos(graph,&end);
    flag=SearchPath_A(graph,&start,&end,&path);                        //节点start到end的路径
    printf("Path:\n");
    RevPath(path);
    PriPath(path);
    printf("\nStep=%ld,Status=%d\n", LengthOfPath(path) - 1, flag);
    printf("==================\n");
    ClearPath(path);                 
}